import java.util.Arrays;

class Solution1 {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n][3];
        int[][] g = new int[n][3];
        f[0][0] = -prices[0];
        f[0][1] = f[0][2] = Integer.MIN_VALUE / 2;
        g[0][1] = g[0][2] = Integer.MIN_VALUE / 2;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j - 1 >= 0) {
                    g[i][j] = Math.max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < 3; i++) {
            max = Math.max(max, g[n - 1][i]);
        }
        return max;
    }
}

class Solution2 {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[][] f = new int[n][k];
        int[][] g = new int[n][k];
        f[0][0] = -prices[0];
        for (int i = 0; i < k; i++) {
            f[0][i] = Integer.MIN_VALUE / 2;
            g[0][i] = Integer.MIN_VALUE / 2;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < k; j++) {
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j - 1 >= 0) {
                    g[i][j] = Math.max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < k; i++) {
            max = Math.max(max, g[n - 1][i]);
        }
        return max;
    }
}

class Solution3 {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n+1];
        for(int i = 1; i<n; i++) {
            dp[i] = Math.max(nums[i], dp[i-1] + nums[i-1]);
        }
        int ret = Integer.MIN_VALUE;
        for(int i = 1; i<=n; i++) {
            ret = Math.max(ret, dp[i]);
            System.out.print(dp[i] + " ");
        }
        return ret;
    }
}

class Solution4 {
    public int maxSubArray(int[] nums) {
        int sum = 0;  //当前和
        int max = Integer.MIN_VALUE;
        for(int i = 0; i<nums.length; i++) {
            sum = Math.max(sum + nums[i], nums[i]);
            max = Math.max(max,sum);
        }
        return max;
    }
}

class Solution5 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length, n2 = nums2.length;
        int[] nums3 = new int[n1+n2];
        int i = 0, j = 0, k = 0;
        while(i<n1 && j<n2) {
            if(nums1[i] < nums2[j]) {
                nums3[k++] = nums1[i++];
            }else {
                nums3[k++] = nums2[j++];
            }
        }
        while(i<n1) {
            nums3[k++] = nums1[i++];
        }
        while(j<n2) {
            nums3[k++] = nums2[j++];
        }
        //System.out.println(Arrays.toString(nums3));
        int s = n1+n2;
        if(s%2==1) {
            return nums3[s/2];
        }else {
            return (nums3[s/2-1] + nums3[s/2])/2.0;
        }
    }
}

class Solution6 {
    public int reverse(int y) {
        long x = y;
        boolean flag = false;
        if(x < 0) {
            flag = true;
            x = -x;
        }
        String str = String.valueOf(x);
        str = new StringBuffer(str).reverse().toString();
        long ret = Long.valueOf(str);
        System.out.println(str);
        System.out.println(ret);
        if(ret > (long)Integer.MAX_VALUE) return 0;
        if(flag) {
            ret =  -ret;
        }

        return (int)ret;
    }
}

class Solution {
    public int myAtoi(String s) {
        int i = 0;
        StringBuffer str = new StringBuffer();
        while(s.charAt(i) == ' ') {
            i++;
        }
        s = s.substring(i);
        int flag = 0;
        for(i = 0; i<s.length();i++) {
            char ch = s.charAt(i);
            if(ch == '-') flag = 1;
            else if(ch>='0' && ch<='9') {
                str.append(ch);
            }else {
                break;
            }
        }

        long ret = 0;
        for(i=0; i<str.length(); i++) {
            ret = ret*10 + str.charAt(i)-'0';
        }
        System.out.println(str);

        System.out.println(ret);
        while(ret >= Integer.MAX_VALUE) {
            ret = Integer.MAX_VALUE - ret;
        }
        System.out.println(ret);
        if(flag == 1) ret = -ret;
        return (int)ret;
    }
}

public class Test {

    public static void main1(String[] args) {
        int ret = new Solution().myAtoi("-91283472332");
        System.out.println(ret);
    }
}
